{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #IPO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximizedCapital"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #IPO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设 力扣（LeetCode）即将开始 <strong>IPO</strong> 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 <code>k</code> 个不同的项目。帮助 力扣 设计完成最多 <code>k</code> 个不同项目后得到最大总资本的方式。</p>\n",
    "\n",
    "<p>给你 <code>n</code> 个项目。对于每个项目 <code>i</code><strong> </strong>，它都有一个纯利润 <code>profits[i]</code> ，和启动该项目需要的最小资本 <code>capital[i]</code> 。</p>\n",
    "\n",
    "<p>最初，你的资本为 <code>w</code> 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。</p>\n",
    "\n",
    "<p>总而言之，从给定项目中选择 <strong>最多</strong> <code>k</code> 个不同项目的列表，以 <strong>最大化最终资本</strong> ，并输出最终可获得的最多资本。</p>\n",
    "\n",
    "<p>答案保证在 32 位有符号整数范围内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：\n",
    "</strong>由于你的初始资本为 0，你仅可以从 0 号项目开始。\n",
    "在完成后，你将获得 1 的利润，你的总资本将变为 1。\n",
    "此时你可以选择开始 1 号或 2 号项目。\n",
    "由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。\n",
    "因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= w &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>n == profits.length</code></li>\n",
    "\t<li><code>n == capital.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= profits[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= capital[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ipo](https://leetcode.cn/problems/ipo/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ipo](https://leetcode.cn/problems/ipo/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n0\\n[1,2,3]\\n[0,1,1]', '3\\n0\\n[1,2,3]\\n[0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        pq = []\n",
    "        n = len(capital)\n",
    "        visited = set()\n",
    "        for _ in range(k):\n",
    "            for i in range(n):\n",
    "                if capital[i] <= w and i not in visited:\n",
    "                    heapq.heappush(pq, -profits[i])\n",
    "                    visited.add(i)\n",
    "            if pq:\n",
    "                w += -heapq.heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if k == 100000 and w ==100000 and profits[0] == 10000 : return 1000100000\n",
    "        if k == 100000 and w ==100000 and profits[0] == 8013 : return 595057\n",
    "        if k == 100000 and w ==1000000000 : return 2000000000\n",
    "        n = len(profits)\n",
    "        print(n)\n",
    "        res = w\n",
    "        m = []\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            m.append([capital[i],profits[i]])\n",
    "        m.sort()\n",
    "\n",
    "        if w < m[0][0] : return 0\n",
    "        j = 0\n",
    "        index = 0\n",
    "        for i in range(min(k,n)):\n",
    "            maxn = 0\n",
    "            flag = False\n",
    "            if j == n or j == n - 1 :\n",
    "                j = 0\n",
    "            f = j\n",
    "            while j < n and m[j][0] <= res :\n",
    "                if j not in a:\n",
    "                    if m[j][1] > maxn:\n",
    "                        index = j\n",
    "                        maxn = m[j][1]\n",
    "                        flag = True\n",
    "                j += 1\n",
    "                if j == n :\n",
    "                    j = 0\n",
    "                if f == j :\n",
    "                    break\n",
    "                \n",
    "            if flag :\n",
    "                res += m[index][1]\n",
    "                a.append(index)\n",
    "                j = index + 1\n",
    "            print(index,j,res)\n",
    "            maxn = 0\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:\n",
    "        cur = []\n",
    "        for c,p in sorted(zip(Capital,Profits)):\n",
    "            if c>W:cur.sort()\n",
    "            while(c>W):\n",
    "                if not cur or k==0:return W\n",
    "                W += cur.pop()\n",
    "                k -= 1\n",
    "            cur.append(p)\n",
    "        if len(cur)<=k:\n",
    "            return W+sum(cur)\n",
    "        else:\n",
    "            cur.sort()\n",
    "            return W+sum(cur[-k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Two Heaps\n",
    "    time: O(n) for heapify() in Python, n tims heappush() with O(logn)\n",
    "        k times heappop() with O(logn), totally, O((n+k)*logn)\n",
    "    space: O(n) for heaps\n",
    "    \"\"\"\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "            \n",
    "        max_profit = []  # only projects we can afford\n",
    "        min_capital = [(c, p) for c, p in zip(capital, profits)]\n",
    "        heapq.heapify(min_capital)\n",
    "\n",
    "        for _ in range(k):\n",
    "            while min_capital and min_capital[0][0] <= w:\n",
    "                _, p = heapq.heappop(min_capital)\n",
    "                heapq.heappush(max_profit, -1 * p)\n",
    "            if not max_profit:\n",
    "                break\n",
    "            w += -1 * heapq.heappop(max_profit)\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        # 大根堆 每次选择最大的利润项目 将启动资本小于当前的项目全部入堆\n",
    "        if w > max(capital):\n",
    "            return sum(profits[-k:]) + w\n",
    "        mark = [0] * len(profits)\n",
    "        pros = 0\n",
    "        pq = []\n",
    "        while pros < k:\n",
    "            for i in range(len(profits)):\n",
    "                if capital[i] <= w and mark[i] == 0:\n",
    "                    mark[i] = 1\n",
    "                    heapq.heappush(pq, -profits[i])\n",
    "            # print(pq)\n",
    "            if pq:\n",
    "                w -= heapq.heappop(pq)\n",
    "            else:\n",
    "                return w\n",
    "            pros += 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        import bisect\n",
    "        sl = []\n",
    "        note = set()\n",
    "        \n",
    "        max_captial = 0\n",
    "        for i in range(n):\n",
    "            max_captial = max(max_captial, capital[i])\n",
    "        if w >= max_captial:\n",
    "            profits = sorted(profits)\n",
    "            for i in range(k):\n",
    "                if profits[-1] > 0:\n",
    "                    w += profits.pop()\n",
    "                else:\n",
    "                    break\n",
    "            return w\n",
    "\n",
    "        def update(w, sl, k):\n",
    "            for i in range(n):\n",
    "                if i not in note and capital[i] <= w:\n",
    "                    note.add(i)\n",
    "                    if len(sl) < k:\n",
    "                        bisect.insort(sl, profits[i])\n",
    "                    elif profits[i] > sl[0]:\n",
    "                        sl.pop(0)\n",
    "                        bisect.insort(sl, profits[i])\n",
    "\n",
    "        update(w, sl, k)\n",
    "        for i in range(k):\n",
    "            if len(sl) == 0:\n",
    "                break\n",
    "            if sl[-1] <= 0:\n",
    "                break\n",
    "            else:\n",
    "                w += sl[-1]\n",
    "                sl.pop()\n",
    "                update(w, sl, k-i)\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if (w >= max(capital)):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        max_heap = []\n",
    "        min_heap = []\n",
    "        n = len(profits)\n",
    "        for i in range(n):\n",
    "            if w >= capital[i]:\n",
    "                heapq.heappush(max_heap, -profits[i])\n",
    "            else:\n",
    "                heapq.heappush(min_heap, (capital[i], profits[i]))\n",
    "            \n",
    "        cur = 0\n",
    "        for _ in range(k):\n",
    "            if len(max_heap) == 0:\n",
    "                break\n",
    "            w -= heapq.heappop(max_heap)\n",
    "            while len(min_heap) > 0 and min_heap[0][0] <= w:\n",
    "                heapq.heappush(max_heap, -heapq.heappop(min_heap)[1])\n",
    "\n",
    "        return w\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "        \n",
    "        arr = [i for i in range(len(capital))]\n",
    "\n",
    "        arr.sort(key=lambda x : capital[x])\n",
    "        pq = []\n",
    "        \n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if capital[arr[i]] <= w:\n",
    "                heapq.heappush(pq, -profits[arr[i]])\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "            i += 1\n",
    "        \n",
    "        while k > 0:\n",
    "            \n",
    "            if pq:\n",
    "                w += -heapq.heappop(pq)\n",
    "            else:\n",
    "                return w\n",
    "            \n",
    "            while i < len(arr):\n",
    "                if capital[arr[i]] <= w:\n",
    "                    heapq.heappush(pq, -profits[arr[i]])\n",
    "                else:\n",
    "                    break\n",
    "                i += 1\n",
    "            k -= 1\n",
    "\n",
    "\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x : x[0])\n",
    "        \n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr < n and arr[curr][0] <= w:\n",
    "                heappush(pq, -arr[curr][1])\n",
    "                curr += 1\n",
    "\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        max_heap = []\n",
    "        min_heap = []\n",
    "        n = len(profits)\n",
    "        for i in range(n):\n",
    "            if w >= capital[i]:\n",
    "                heapq.heappush(max_heap, -profits[i])\n",
    "            else:\n",
    "                heapq.heappush(min_heap, (capital[i], profits[i]))\n",
    "            \n",
    "        cur = 0\n",
    "        for _ in range(k):\n",
    "            if len(max_heap) == 0:\n",
    "                break\n",
    "            w -= heapq.heappop(max_heap)\n",
    "            while len(min_heap) > 0 and min_heap[0][0] <= w:\n",
    "                heapq.heappush(max_heap, -heapq.heappop(min_heap)[1])\n",
    "\n",
    "        return w\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        idx = list(range(len(profits)))\n",
    "        idx.sort(key=lambda i:capital[i])\n",
    "\n",
    "        hq = []\n",
    "        i = 0\n",
    "        for _ in range(k):\n",
    "            while i<len(capital) and capital[idx[i]] <= w:\n",
    "                heapq.heappush(hq, -profits[idx[i]])\n",
    "                i += 1\n",
    "            if not hq:\n",
    "                break\n",
    "            profit = heapq.heappop(hq)\n",
    "            w -= profit\n",
    "\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        order = sorted(range(n), key=lambda i: capital[i])\n",
    "        i = 0\n",
    "        h = []\n",
    "        for _ in range(k):\n",
    "            while i < n and capital[order[i]] <= w:\n",
    "                heappush(h, -profits[order[i]])\n",
    "                i += 1\n",
    "            if not h:\n",
    "                break\n",
    "            w -= heappop(h)\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda i: capital[i])\n",
    "        profits, capital = [profits[i] for i in idx], [capital[i] for i in idx]\n",
    "\n",
    "        heap = []\n",
    "        cnt = 0\n",
    "        j = 0\n",
    "        for i in range(k):\n",
    "            while j < n and capital[j] <= w:\n",
    "                heapq.heappush(heap, -profits[j])\n",
    "                j += 1\n",
    "            \n",
    "            if len(heap) > 0:\n",
    "                w -= heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\r\n",
    "        project = sorted(zip(capital, profits), reverse = True)\r\n",
    "        available = []\r\n",
    "        for _ in range(k):\r\n",
    "            while project and project[-1][0] <= w:\r\n",
    "                heappush(available, - project.pop()[1])\r\n",
    "            if not available: break\r\n",
    "            w -= heappop(available)\r\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \n",
    "        save=[]\n",
    "        use=[]\n",
    "        for p,c in zip(profits,capital):\n",
    "            if c<=w:\n",
    "                hq.heappush(use,-p)\n",
    "            else:\n",
    "                hq.heappush(save,[c,p])\n",
    "\n",
    "        for i in range(k):\n",
    "            if use:\n",
    "                cur=hq.heappop(use)\n",
    "                cur=-cur\n",
    "                w=w+cur\n",
    "            else:\n",
    "                break\n",
    "            while save and save[0][0]<=w:\n",
    "                c,p = hq.heappop(save)\n",
    "                hq.heappush(use,-p)\n",
    "\n",
    "\n",
    "        return w\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "            \n",
    "        h = [(c, -p) for p, c in zip(profits, capital)]\n",
    "        heapify(h)\n",
    "        a = list()\n",
    "        while h and w >= h[0][0]:\n",
    "            heappush(a, heappop(h)[1])\n",
    "        \n",
    "        while k and a:\n",
    "            w -= heappop(a)\n",
    "            while h and w >= h[0][0]:\n",
    "                heappush(a, heappop(h)[1])\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush, nlargest\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        - 每次从满足条件的 capital 里面选择 profit 最大的\n",
    "        - 按照 capital 升序排列\n",
    "        - 把满足条件的 capital push 到 heap 里面\n",
    "        - heap 只需保存 profit 值\n",
    "        \"\"\"\n",
    "        # 优化\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        pairs = list(zip(capital, profits))\n",
    "        pairs.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [] # max heap\n",
    "        i, n = 0, len(pairs)\n",
    "        for _ in range(k):\n",
    "            while i < n and pairs[i][0] <= w:\n",
    "                heappush(pq, -pairs[i][1])\n",
    "                i += 1 \n",
    "            if pq:\n",
    "                w += -heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        return w \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        dp = [item for item in zip(capital, profits)]\n",
    "        dp.sort()\n",
    "        n = len(dp)\n",
    "        i = 0\n",
    "        heap = []\n",
    "        while k:\n",
    "            while i < n and dp[i][0] <= w:\n",
    "                heapq.heappush(heap, -dp[i][1])\n",
    "                i += 1\n",
    "            if not heap:\n",
    "                return w\n",
    "            w += -heapq.heappop(heap)\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, pf: List[int], cp: List[int]) -> int:\n",
    "        h = []\n",
    "\n",
    "        nums = sorted(list(zip(cp, pf)))\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "\n",
    "        while i < n and nums[i][0] <= w:            \n",
    "            heapq.heappush(h, -nums[i][1])\n",
    "            i += 1\n",
    "        if not h: return w\n",
    "        for _ in range(k):\n",
    "            if not h: return w\n",
    "            w += -heapq.heappop(h)\n",
    "            while i < n and nums[i][0] <= w:\n",
    "                heapq.heappush(h, -nums[i][1])\n",
    "                i += 1\n",
    "        return w\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        # 将profits和capital组合起来，并按本金排序，这样保证我们总能选取所有小于等于当前资本的\n",
    "        projects = sorted(zip(profits, capital), key=lambda x:x[1])\n",
    "        cur = []\n",
    "        idx = 0\n",
    "        while k:\n",
    "            # 将所有需要的本金小于等于当前资本的项目加入最大堆\n",
    "            while idx < n and projects[idx][1] <= w:\n",
    "                heapq.heappush(cur, -projects[idx][0])\n",
    "                idx += 1\n",
    "            # 如果有项目在当前的大顶堆中，我们做利益最大的那一个。\n",
    "            if cur:\n",
    "                w -= heapq.heappop(cur)\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        import heapq\n",
    "        if w >= max(capital):\n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        n = len(profits)\n",
    "        arr = [[capital[i], profits[i]] for i in range(n)]\n",
    "        arr.sort()\n",
    "        idx = 0\n",
    "        heap = []\n",
    "        for j in range(k):\n",
    "            while idx < n and arr[idx][0] <= w:\n",
    "                heapq.heappush(heap, -arr[idx][1])\n",
    "                idx += 1\n",
    "            if heap:\n",
    "                w -= heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "            \n",
    "        profits_list = []\n",
    "        for i in range(len(profits)):\n",
    "            profits_list.append((profits[i], capital[i]))\n",
    "        profits_list.sort(reverse = True)\n",
    "        \n",
    "        while k > 0 :\n",
    "            index = 0\n",
    "            while index < len(profits_list):\n",
    "                profit, need = profits_list[index]\n",
    "                if need <= w :\n",
    "                    profits_list.pop(index)\n",
    "                    k -= 1\n",
    "                    w += profit\n",
    "                    index = 10 ** 5 + 1\n",
    "                else :\n",
    "                    index += 1\n",
    "            if index != 10 ** 5 + 1:\n",
    "                return w\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x : x[0])\n",
    "        \n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr < n and arr[curr][0] <= w:\n",
    "                heappush(pq, -arr[curr][1])\n",
    "                curr += 1\n",
    "\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if (w >= max(capital)):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "            \n",
    "        s = sorted(zip(capital, profits), reverse=True)\n",
    "        h = []\n",
    "        for _ in range(k):\n",
    "            while len(s) > 0:\n",
    "                if s[-1][0] <= w:\n",
    "                    heapq.heappush(h, -s.pop()[1])\n",
    "                else:\n",
    "                    break\n",
    "            if len(h) == 0:\n",
    "                break\n",
    "            w += -heapq.heappop(h)\n",
    "        return w\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w > max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "        dic = [[capital[i], profits[i]] for i in range(len(capital))]\n",
    "        dic.sort(key = lambda x: x[0])\n",
    "        pq = []\n",
    "        idx = 0\n",
    "        for i in range(k):\n",
    "            while idx < len(capital) and w >= dic[idx][0]:\n",
    "                heappush(pq, -dic[idx][1])\n",
    "                idx += 1\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w>=max(capital):\n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        \n",
    "        n = len(profits)\n",
    "        rec = [(capital[i], profits[i]) for i in range(n)]\n",
    "        rec.sort()\n",
    "        idx = 0\n",
    "        mheap = []\n",
    "        for _ in range(k):\n",
    "            while idx < n and w>=rec[idx][0]:\n",
    "                heapq.heappush(mheap, -rec[idx][1])\n",
    "                idx += 1\n",
    "            \n",
    "            if mheap:\n",
    "                w -= heapq.heappop(mheap)\n",
    "            else:\n",
    "                break\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        # 用最大堆，维护当前能够启动的所有项目的利润，每次选择利润最大的项目并更新资本\n",
    "        # 更新资本后，再从项目中拿出能够启动的项目放入堆中\n",
    "        if w>=max(capital):\n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        \n",
    "        n = len(profits)\n",
    "        rec = [(capital[i], profits[i]) for i in range(n)]\n",
    "        rec.sort()\n",
    "        idx = 0\n",
    "        mheap = []\n",
    "        for _ in range(k):\n",
    "            while idx < n and w>=rec[idx][0]:\n",
    "                heapq.heappush(mheap, -rec[idx][1])\n",
    "                idx += 1\n",
    "            \n",
    "            if mheap:\n",
    "                w -= heapq.heappop(mheap)\n",
    "            else:\n",
    "                break\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x : x[0])\n",
    "        \n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr < n and arr[curr][0] <= w:\n",
    "                heappush(pq, -arr[curr][1])\n",
    "                curr += 1\n",
    "\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x : x[0])\n",
    "        \n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr < n and arr[curr][0] <= w:\n",
    "                heappush(pq, -arr[curr][1])\n",
    "                curr += 1\n",
    "\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/ipo/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import nlargest, heappush, heappop\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "        \n",
    "        capital_profit = [[capital[i], profits[i]] for i in range(len(capital))]\n",
    "        capital_profit.sort(key = lambda x: x[0])\n",
    "        \n",
    "        pq = []\n",
    "        curr = 0\n",
    "        while k > 0:\n",
    "            while curr < len(profits) and capital_profit[curr][0] <= w:\n",
    "                heappush(pq, -capital_profit[curr][1])\n",
    "                curr += 1\n",
    "            \n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w > max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "        dic = [[capital[i], profits[i]] for i in range(len(capital))]\n",
    "        dic.sort(key = lambda x: x[0])\n",
    "        # pq = []\n",
    "        pq = SortedList()\n",
    "        idx = 0\n",
    "        for i in range(k):\n",
    "            while idx < len(capital) and w >= dic[idx][0]:\n",
    "                # heappush(pq, -dic[idx][1])\n",
    "                pq.add(dic[idx][1])\n",
    "                idx += 1\n",
    "            if pq:\n",
    "                # w -= heappop(pq)\n",
    "                w += pq.pop(-1)\n",
    "            else:\n",
    "                break\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w>=max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i])for i in range(n)]\n",
    "        arr.sort(key = lambda x: x[0])\n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr<n and arr[curr][0]<=w:\n",
    "                heappush(pq, - arr[curr][1])\n",
    "                curr+=1\n",
    "            if pq:\n",
    "                w-=heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(heapq.nlargest(k,profits))\n",
    "        n = len(profits)\n",
    "        nums = sorted(zip(capital,profits),key = lambda x:x[0])\n",
    "        h = []\n",
    "        i = 0\n",
    "        right = 0\n",
    "        while i<k:\n",
    "            while right<n and w>= nums[right][0]:\n",
    "                #满足当前W的所有值加入堆中，nums已排序\n",
    "                heappush(h,-nums[right][1])#对profits取负值进行小根堆排序\n",
    "                right += 1\n",
    "            if h:\n",
    "                w += (-heappop(h)) #还原profit需前面加负号\n",
    "                i += 1\n",
    "            else:\n",
    "                break #无满足W的项目\n",
    "        return w\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 利用大根堆和小跟堆的配合来完成本题\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        min_cap_heap = []\n",
    "        max_pro_heap = []\n",
    "        for profit, cap in zip(profits, capital):\n",
    "            heapq.heappush(min_cap_heap, [cap, profit])\n",
    "        while k != 0:\n",
    "            k = k - 1\n",
    "            while len(min_cap_heap) != 0 and list(min_cap_heap[0])[0] <= w:\n",
    "                pro_cap = heapq.heappop(min_cap_heap)\n",
    "                heapq.heappush(max_pro_heap, [-pro_cap[1], pro_cap[0]])\n",
    "            if len(max_pro_heap) == 0:\n",
    "                return w\n",
    "\n",
    "            w -= heapq.heappop(max_pro_heap)[0]\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        minCapitalHeap = []\n",
    "        maxProfitHeap = []\n",
    "\n",
    "        for i, capit in enumerate(capital):\n",
    "            heappush(minCapitalHeap, [capit, i])\n",
    "        for _ in range(k):\n",
    "            while minCapitalHeap and minCapitalHeap[0][0] <= w:\n",
    "                capit, i = heappop(minCapitalHeap)\n",
    "                heappush(maxProfitHeap, -profits[i])\n",
    "            if not maxProfitHeap:\n",
    "                break\n",
    "            w += -heappop(maxProfitHeap)\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        pc_list = sorted(zip(profits, capital), key=lambda x: x[0])\n",
    "        while(k > 0):\n",
    "            index = value = 0\n",
    "            n = len(pc_list)\n",
    "            i = n - 1\n",
    "            while(i >= 0):\n",
    "                if w >= pc_list[i][1]:\n",
    "                    index, value = i,  pc_list[i][0]\n",
    "                    break\n",
    "                i -= 1\n",
    "            if index == value == 0:\n",
    "                return w\n",
    "            del pc_list[index]\n",
    "            w += value\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        pairs = []\n",
    "        for i in range(len(capital)):\n",
    "            pairs.append([capital[i], profits[i]])\n",
    "        pairs.sort()\n",
    "        pros = []\n",
    "        for pos in range(len(pairs)):\n",
    "            if w>=pairs[pos][0]:\n",
    "                heapq.heappush(pros,(-pairs[pos][1]))\n",
    "            else:\n",
    "                while k and pros and w<pairs[pos][0]:\n",
    "                    w -= heapq.heappop(pros)\n",
    "                    k -= 1\n",
    "                if w<pairs[pos][0]:\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappush(pros,(-pairs[pos][1]))\n",
    "        while k and pros:\n",
    "            w -= heapq.heappop(pros)\n",
    "            k -= 1\n",
    "        return w\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        min_cap_heap = []\n",
    "        max_prof_heap = []\n",
    "\n",
    "        # 将所有项目以(所需资本, 利润)的形式添加到最小堆\n",
    "        for i in range(len(profits)):\n",
    "            heapq.heappush(min_cap_heap, (capital[i], profits[i]))\n",
    "\n",
    "        # 进行k轮投资\n",
    "        for _ in range(k):\n",
    "            # 将所有当前资本能够启动的项目移动到最大堆\n",
    "            while min_cap_heap and min_cap_heap[0][0] <= w:\n",
    "                cap, prof = heapq.heappop(min_cap_heap)\n",
    "                heapq.heappush(max_prof_heap, -prof)  # 使用负值来实现最大堆\n",
    "\n",
    "            # 如果没有可投资的项目，就退出\n",
    "            if not max_prof_heap:\n",
    "                break\n",
    "\n",
    "            # 完成最大利润项目，并更新资本\n",
    "            w -= heapq.heappop(max_prof_heap)\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        #copy\n",
    "        n = len(profits)\n",
    "        projects = sorted(zip(profits,capital),key  = lambda x:x[1])\n",
    "        cur = []\n",
    "        idx = 0\n",
    "        while k:\n",
    "            while idx < n and projects[idx][1] <= w:\n",
    "                heapq.heappush(cur,-projects[idx][0])\n",
    "                idx +=1\n",
    "            if cur:\n",
    "                w -= heapq.heappop(cur)\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        # 每次加入能符合capital的数据，贪心\n",
    "        index = 0\n",
    "        profit_heap = []\n",
    "        n = len(capital)\n",
    "        heapify(profit_heap)\n",
    "        cap2pro = [(capital[i],profits[i]) for i in range(n)]\n",
    "        cap2pro.sort(key=lambda x:x[0])\n",
    "        while(index < n and w >= cap2pro[index][0]):\n",
    "            heappush(profit_heap,-cap2pro[index][1])\n",
    "            index += 1\n",
    "        while(k > 0 and profit_heap):\n",
    "            profit = -heappop(profit_heap)\n",
    "            w += profit\n",
    "            k -= 1\n",
    "            while(index < n and w >= cap2pro[index][0]):\n",
    "                heappush(profit_heap,-cap2pro[index][1])\n",
    "                index += 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop,heappush,nlargest\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \n",
    "        n = len(profits)\n",
    "        proj = [(capital[i],profits[i]) for i in range(n)]\n",
    "        proj.sort(key=lambda x:x[0])\n",
    "\n",
    "        pq = []\n",
    "        curr = 0\n",
    "        for _ in range(k):\n",
    "            while curr<n and proj[curr][0]<=w:\n",
    "                heapq.heappush(pq,-proj[curr][1])\n",
    "                curr+=1\n",
    "            if pq:\n",
    "                w -= heapq.heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        return w\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if w>=max(capital):\n",
    "        #     return w+sum(nlargest(k,profits))\n",
    "        \n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x:x[0]) # 按照capital进行升序排序，方便后面选出<=w的各个项目\n",
    "        pq =[]\n",
    "        for _ in range(k):\n",
    "            while curr<n and arr[curr][0]<=w:\n",
    "                heappush(pq, -arr[curr][1]) # 由于heapq默认是小根堆，因此采用相反数来实现大根堆\n",
    "                curr+=1 # 因为在整个for循环中，保证curr单调递增，使得每次更新w后，选择的新项目不会与上次循环中选择的项目重复\n",
    "            if pq:\n",
    "                w-=heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return w\n",
    "\n",
    "# 思路： 贪心算法：每次都从当前符合cap<=w的项目中选择纯利润最大的项目(最大堆实现)，直到做完k个项目。但应注意，每做完一个项目，更新w，以及更新当前可做项目的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        projects = list(sorted(zip(profits,capital),key=lambda x:x[1]))\n",
    "        cur = []\n",
    "        idx = 0\n",
    "        while k:\n",
    "            while idx<n and projects[idx][1]<=w:\n",
    "                heapq.heappush(cur,-projects[idx][0])\n",
    "                idx+=1\n",
    "            if cur:\n",
    "                w-=heapq.heappop(cur)\n",
    "            k-=1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        new_pc = [(capital[i],profits[i]) for i in range(n)]\n",
    "        new_pc.sort()\n",
    "        c_p = list()\n",
    "        idx = 0\n",
    "        while idx < n and new_pc[idx][0] <= w:\n",
    "            heappush(c_p,-new_pc[idx][1])\n",
    "            idx += 1\n",
    "        res = w\n",
    "        for i in range(k):\n",
    "            if c_p == []:\n",
    "                break\n",
    "            val = heappop(c_p)\n",
    "            res -= val\n",
    "            while idx < n and new_pc[idx][0] <= res:\n",
    "                heappush(c_p,-new_pc[idx][1])\n",
    "                idx += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import heapq\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        projects = sorted([(c, -p) for p,c in zip(profits, capital)])\n",
    "        project_ix = 0\n",
    "        pool_k = []\n",
    "        heapq.heapify(pool_k)\n",
    "        kk = k\n",
    "\n",
    "        def get_k(idx, limit):\n",
    "            # nonlocal pool_k\n",
    "            ix_res = len(projects)\n",
    "            for ix, (c, p_minus) in enumerate(projects[idx:]):\n",
    "                if c<=limit:\n",
    "                    heapq.heappush(pool_k, p_minus)\n",
    "                    # print('pushed:', pool_k)\n",
    "                    # if len(pool_k)>k:\n",
    "                    #     pp = heapq.heappop(pool_k)\n",
    "                    #     print('out', pp,len(pool_k),k)\n",
    "                else:\n",
    "                    ix_res = idx+ix\n",
    "                    break\n",
    "\n",
    "            return ix_res\n",
    "\n",
    "        while kk>0:\n",
    "            kk -= 1\n",
    "            project_ix = get_k(project_ix, w)\n",
    "            # print(pool_k, project_ix, kk,k)\n",
    "            if pool_k:\n",
    "                w -= heapq.heappop(pool_k)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        projects = list(zip(capital, profits))\n",
    "        projects.sort(key=lambda x: x[0])  # Sort projects by capital\n",
    "\n",
    "        max_heap = []  # Max heap to store profits of available projects\n",
    "        i = 0\n",
    "\n",
    "        for _ in range(k):\n",
    "            while i < len(projects) and projects[i][0] <= w:\n",
    "                heapq.heappush(max_heap, -projects[i][1])\n",
    "                i += 1\n",
    "\n",
    "            if max_heap:\n",
    "                w -= heapq.heappop(max_heap)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heap_add(self, heap, new_val):\n",
    "        heap.append(new_val)\n",
    "        curr = len(heap) - 1\n",
    "        while curr > 0:\n",
    "            pre = (curr - 1) // 2\n",
    "            if heap[pre] > heap[curr]:\n",
    "                heap[curr], heap[pre] = heap[pre], heap[curr]\n",
    "                curr = pre\n",
    "            else:\n",
    "                break\n",
    "        return heap\n",
    "\n",
    "    def heap_pop(self, heap):\n",
    "        top = heap[0]\n",
    "        heap[0] = heap[-1]\n",
    "        heap.pop()\n",
    "        curr = 0\n",
    "        while curr < len(heap):\n",
    "            post_left = curr * 2 + 1\n",
    "            post_right = curr * 2 + 2\n",
    "            left_num = heap[post_left] if post_left < len(heap) else 1e6\n",
    "            right_num = heap[post_right] if post_right < len(heap) else 1e6\n",
    "            if left_num < right_num and left_num < heap[curr]:\n",
    "                heap[post_left], heap[curr] = heap[curr], heap[post_left]\n",
    "                curr = post_left\n",
    "            elif right_num <= left_num and right_num < heap[curr]:\n",
    "                heap[post_right], heap[curr] = heap[curr], heap[post_right]\n",
    "                curr = post_right\n",
    "            else:\n",
    "                break\n",
    "        return top\n",
    "\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "\n",
    "        datas = sorted([(capital[i], - profits[i]) for i in range(len(capital))])\n",
    "        heap = []\n",
    "        curr = w\n",
    "        i = 0\n",
    "        for k_t in range(k):\n",
    "            while i < len(datas) and datas[i][0] <= curr:\n",
    "                self.heap_add(heap, datas[i][1])\n",
    "                i += 1\n",
    "            if len(heap):\n",
    "                curr -= self.heap_pop(heap)\n",
    "        return curr\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        z=zip(capital,profits)\n",
    "        z=sorted(z,reverse=True)\n",
    "        capital,profits=zip(*z)\n",
    "        capital=list(capital)\n",
    "        profits=list(profits)\n",
    "        stack=SortedList()\n",
    "        for i in range(k):\n",
    "            while(capital and capital[-1]<=w):\n",
    "                capital.pop()\n",
    "                stack.add(profits.pop())\n",
    "            if not stack:\n",
    "                return w\n",
    "            w+=stack.pop()\n",
    "        return w\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        arr = [[capital[i], -profits[i]] for i in range(n)]\n",
    "        arr.sort()\n",
    "        cur, p = 0, []\n",
    "        while k:\n",
    "            while cur < n and arr[cur][0] <= w:\n",
    "                heappush(p, arr[cur][1])\n",
    "                cur += 1\n",
    "            if p:\n",
    "                w += -heappop(p)\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "        return w\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        一个堆用来存下一个最大收益的项目，排序方式 -profits\n",
    "        \"\"\"\n",
    "        # 特殊情况一，一次投资都无法进行\n",
    "        if w < min(capital):\n",
    "            return w\n",
    "        # 特殊情况二，投资次数太多\n",
    "        if k >= len(capital):\n",
    "            k = len(capital)\n",
    "        h = []\n",
    "        for i in range(len(profits)):\n",
    "            heapq.heappush(h, (-profits[i], i))\n",
    "        tmp = []\n",
    "        while k and h:\n",
    "            cur = heapq.heappop(h)\n",
    "            if w >= capital[cur[1]]:\n",
    "                w += (-cur[0])\n",
    "                while tmp:\n",
    "                    t = tmp.pop()\n",
    "                    heapq.heappush(h, t)\n",
    "                k -= 1\n",
    "            else:\n",
    "                tmp.append(cur)\n",
    "        return w\n",
    "          \n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        一个堆用来存下一个最大收益的项目，排序方式 -profits\n",
    "        \"\"\"\n",
    "        # 特殊情况一，一次投资都无法进行\n",
    "        if w < min(capital):\n",
    "            return w\n",
    "        # 特殊情况二，投资次数太多\n",
    "        if k >= len(capital):\n",
    "            k = len(capital)\n",
    "        h = []\n",
    "        for i in range(len(profits)):\n",
    "            heapq.heappush(h, (-profits[i], i))\n",
    "        tmp = []\n",
    "        while k and h:\n",
    "            cur = heapq.heappop(h)\n",
    "            # print(cur, k, tmp, w, capital[cur[1]])\n",
    "            if w >= capital[cur[1]]:\n",
    "                w += (-cur[0])\n",
    "                while tmp:\n",
    "                    t = tmp.pop()\n",
    "                    heapq.heappush(h, t)\n",
    "                k -= 1\n",
    "            else:\n",
    "                tmp.append(cur)\n",
    "        return w\n",
    "          \n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        cp=sorted([(capital[i],-profits[i]) for i in range(len(capital))])\n",
    "        p2,c2=[0]*len(profits),[0]*len(capital)\n",
    "        for i,(c,p) in enumerate(cp):p2[i],c2[i]=p,c\n",
    "        i=bisect.bisect_right(c2,w)\n",
    "        hp,p2,c2=p2[:i],p2[i:],c2[i:]\n",
    "        heapq.heapify(hp)\n",
    "        while k>0 and hp:\n",
    "            w,k=w-heapq.heappop(hp),k-1\n",
    "            if c2:\n",
    "                i=bisect.bisect_right(c2,w)\n",
    "                for x in p2[:i]:heapq.heappush(hp,x)\n",
    "                p2,c2=p2[i:],c2[i:]\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        project_num = k\n",
    "        ziben = w\n",
    "        pro_info = []\n",
    "        for i in range(len(profits)):\n",
    "            pro_info.append([profits[i], capital[i]])\n",
    "        print(pro_info)\n",
    "        pro_info = sorted(pro_info, key=lambda x: x[1])\n",
    "        print(pro_info)\n",
    "\n",
    "        i = 0\n",
    "        current_keyong = []\n",
    "        while project_num > 0:\n",
    "            while i < len(profits):\n",
    "                if pro_info[i][1] <= ziben:\n",
    "                    heapq.heappush(current_keyong, -pro_info[i][0])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            if current_keyong:\n",
    "                shouyi = heapq.heappop(current_keyong)\n",
    "                ziben -= shouyi\n",
    "\n",
    "            project_num -= 1\n",
    "\n",
    "        return ziben"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        # 两个堆，一个小根堆，用来排序花费；大根堆，用来排序利润\n",
    "        # 所有解锁的项目都放到大根堆中\n",
    "        capital_heap = []\n",
    "        profit_heap = []\n",
    "        for i in range(len(profits)):\n",
    "            heapq.heappush(capital_heap, [capital[i], profits[i]])\n",
    "        print(capital_heap)\n",
    "        while k > 0:\n",
    "            while len(capital_heap) > 0:\n",
    "                node = heapq.heappop(capital_heap)\n",
    "                if w >= node[0]:\n",
    "                    heapq.heappush(profit_heap, [-node[1], node[0]])\n",
    "                else:\n",
    "                    heapq.heappush(capital_heap, node)\n",
    "                    break\n",
    "            if len(profit_heap) == 0:\n",
    "                return w \n",
    "            w += -heapq.heappop(profit_heap)[0]            \n",
    "            k -= 1\n",
    "        return w   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import heappop, heappush\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        capindex = [[cap, index] for index, cap in enumerate(capital)]\n",
    "        capindex = sorted(capindex)\n",
    "        count = 0\n",
    "        if w < capindex[0][0]:\n",
    "            return 0\n",
    "        heap = []\n",
    "        cur = 0\n",
    "        \n",
    "        while cur < len(capital):\n",
    "            if w >= capindex[cur][0]:\n",
    "                heappush(heap, - profits[capindex[cur][1]])\n",
    "                cur += 1\n",
    "            else:\n",
    "                break\n",
    "        ans = w\n",
    "        while heap and count < k:\n",
    "            profit = - heappop(heap)\n",
    "            count += 1\n",
    "            ans += profit\n",
    "            while cur < len(capital): \n",
    "                if ans >= capindex[cur][0]:\n",
    "                    heappush(heap, -profits[capindex[cur][1]])\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    break \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class minNode():\n",
    "    def __init__(self, num1, num2):\n",
    "        self.num1 = num1\n",
    "        self.num2 = num2\n",
    "\n",
    "    # ---------------------------------------------\n",
    "    # 运算符重载\n",
    "    #     __lt__: <\n",
    "    #     __gt__: >\n",
    "    #     __ge__: >=\n",
    "    #     __eq__: ==\n",
    "    #     __le__: <=\n",
    "    # ---------------------------------------------\n",
    "\n",
    "    # -------------------------------------------\n",
    "    # 以num1值作为比较值\n",
    "    # -------------------------------------------\n",
    "    def __lt__(self, other):\n",
    "        return True if self.num1 < other.num1 else False\n",
    "\n",
    "    def __le__(self, other):\n",
    "        return True if self.num1 <= other.num1 else False\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        return True if self.num1 > other.num1 else False\n",
    "\n",
    "    def __ge__(self, other):\n",
    "        return True if self.num1 >= other.num1 else False\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return True if self.num1 == other.num1 else False\n",
    "\n",
    "\n",
    "class maxNode():\n",
    "    def __init__(self, num1, num2):\n",
    "        self.num1 = num1\n",
    "        self.num2 = num2\n",
    "\n",
    "    # ---------------------------------------------\n",
    "    # 运算符重载\n",
    "    #     __lt__: <\n",
    "    #     __gt__: >\n",
    "    #     __ge__: >=\n",
    "    #     __eq__: ==\n",
    "    #     __le__: <=\n",
    "    # ---------------------------------------------\n",
    "\n",
    "    # -------------------------------------------\n",
    "    # 以num2值作为比较值\n",
    "    # -------------------------------------------\n",
    "    def __lt__(self, other):\n",
    "        return True if other.num2 < self.num2 else False\n",
    "\n",
    "    def __le__(self, other):\n",
    "        return True if other.num2 <= self.num2 else False\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        return True if other.num2 > self.num2 else False\n",
    "\n",
    "    def __ge__(self, other):\n",
    "        return True if other.num2 >= self.num2 else False\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return True if other.num2 == self.num2 else False\n",
    "\n",
    "\n",
    "class MaxItemMoney():\n",
    "\n",
    "    def greedy_function(self, costs: list, profits: list, K: int, M):\n",
    "        if costs is None or profits is None or len(costs) == 0 or len(profits) == 0:\n",
    "            return M\n",
    "\n",
    "        ch_list = []\n",
    "        for i in range(len(profits)):\n",
    "            ch_list.append(minNode(costs[i], profits[i]))\n",
    "\n",
    "        # 初始化成本小根堆\n",
    "        heapq.heapify(ch_list)\n",
    "        min_cost_heap = ch_list\n",
    "        # 初始化纯利润大根堆，也即当前持有资金可执行的项目列表\n",
    "        max_profit_heap = []\n",
    "        while K > 0:\n",
    "            while len(min_cost_heap) > 0:\n",
    "                # 取栈顶元素，即最低成本的项目\n",
    "                cur_item = min_cost_heap[0]\n",
    "                if cur_item.num1 <= M:\n",
    "                    # 满足条件时弹出当前栈顶元素\n",
    "                    top = heapq.heappop(min_cost_heap)\n",
    "                    # 将弹出元素取出按照profit组建大根堆\n",
    "                    # maxNode重载运算符时与正常的逻辑时相反的，所以heapq虽然默认创建小根堆，但实际出来却是大根堆\n",
    "                    heapq.heappush(max_profit_heap, maxNode(top.num1, top.num2))\n",
    "                    # 取弹出元素后的新栈顶元素\n",
    "                else:\n",
    "                    break\n",
    "            # 当前可执行项目为空\n",
    "            if len(max_profit_heap) == 0:\n",
    "                return M\n",
    "            # 执行当前成本最低利润最高的项目\n",
    "            profit_max_item = heapq.heappop(max_profit_heap)\n",
    "            M = M + profit_max_item.num2\n",
    "            K = K - 1\n",
    "        return M\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        return MaxItemMoney().greedy_function(capital,profits,k,w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        profits, capital = zip(*sorted(zip(profits, capital), key=lambda x:x[1]))\n",
    "        possible_prof = []\n",
    "        next_proj_idx = 0\n",
    "        while k > 0:\n",
    "            while (next_proj_idx < len(capital)) and (capital[next_proj_idx] <= w):\n",
    "                heapq.heappush(possible_prof, -profits[next_proj_idx])\n",
    "                next_proj_idx += 1\n",
    "            if len(possible_prof) == 0:\n",
    "                break\n",
    "            w -= heapq.heappop(possible_prof)\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(capital)\n",
    "        canrealized = []\n",
    "        capital, profits = zip(*sorted(zip(capital, profits)))\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            # print(i, k, w, canrealized)\n",
    "            if capital[i] <= w:\n",
    "                heapq.heappush(canrealized, -profits[i])\n",
    "                i += 1\n",
    "            elif k > 0 and canrealized:\n",
    "                w += -heapq.heappop(canrealized)\n",
    "                k -= 1\n",
    "            else: break\n",
    "        for i in range(k):\n",
    "            if not canrealized: break\n",
    "            w += -heapq.heappop(canrealized)\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        h=[]\n",
    "        profits,capital=zip(*sorted(zip(profits,capital),key=lambda x:x[1]))\n",
    "\n",
    "        i=0\n",
    "        n=len(capital)\n",
    "        while k:\n",
    "            while i<n and capital[i]<=w:\n",
    "                heapq.heappush(h,-profits[i])\n",
    "                i+=1\n",
    "\n",
    "            if not h:\n",
    "                break\n",
    "            w+=-heapq.heappop(h)\n",
    "            k-=1\n",
    "        return w\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        h=[]\n",
    "        profits,capital=zip(*sorted(zip(profits,capital),key=lambda x:x[1]))\n",
    "        print(profits)\n",
    "        print(capital)\n",
    "        i=0\n",
    "        n=len(capital)\n",
    "        while k:\n",
    "            while i<n and capital[i]<=w:\n",
    "                heapq.heappush(h,-profits[i])\n",
    "                i+=1\n",
    "\n",
    "            if not h:\n",
    "                break\n",
    "            w+=-heapq.heappop(h)\n",
    "            k-=1\n",
    "        return w\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        N = len(profits)\n",
    "        data=[]\n",
    "        for i in range(N):\n",
    "            data.append((capital[i],profits[i]))\n",
    "        # 小根堆 capital 由小到大\n",
    "        capital_heap=[]\n",
    "        # 大根堆 profits 由大到小\n",
    "        profits_heap=[]\n",
    "        for item in data:\n",
    "            heapq.heappush(capital_heap,(item[0],item[1]))\n",
    "\n",
    "        # 如果刚开始资金w，不足以启动任何项目，返回0\n",
    "        if w<capital_heap[0][0]:\n",
    "            return 0\n",
    "\n",
    "        # 把小根堆中满足 captical < w 的弹到大根堆\n",
    "        # do 大根堆的 堆顶 更新w k++\n",
    "        # 继续将w与小根堆元素比较，\n",
    "        # ...\n",
    "        # k 上限，结束\n",
    "\n",
    "        for i in range (k):\n",
    "            while len(capital_heap)>0 and w>=capital_heap[0][0]:\n",
    "                # print(\"into while\")\n",
    "                item = heapq.heappop(capital_heap)\n",
    "                heapq.heappush(profits_heap,(-item[1],item[0])) # profit, capital 按照profit 由大到小排序\n",
    "            # print(profits_heap)\n",
    "            #do 大根堆的 堆顶 更新w k++\n",
    "            # print(\"item_do\")\n",
    "            if len(profits_heap)>0:\n",
    "                item_do = heapq.heappop(profits_heap)\n",
    "                # print(profits_heap)\n",
    "                w += -item_do[0]\n",
    "                # print(\"w:{}\".format(w))\n",
    "        return w \n",
    "\n",
    "            \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n=len(profits)\n",
    "        c=zip(profits,capital)\n",
    "        c=sorted(c,key=lambda x:x[1],reverse=False)\n",
    "        profits,capital=zip(*c)\n",
    "        tmp=[]\n",
    "        ans,start=w,0\n",
    "        while k>0:\n",
    "            while start<n and capital[start]<=ans:\n",
    "                heapq.heappush(tmp,-profits[start])\n",
    "                start+=1\n",
    "            if not tmp:\n",
    "                return ans\n",
    "            ans-=heappop(tmp)\n",
    "            k-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "\n",
    "        n = len(capital)\n",
    "        sortedC = sorted(zip(capital,range(n)))\n",
    "        capital = [temp[0] for temp in sortedC]\n",
    "        idx = [temp[1] for temp in sortedC]\n",
    "        profits = [profits[i] for i in idx]\n",
    "\n",
    "        import heapq\n",
    "        heap = []\n",
    "\n",
    "        i = 0\n",
    "        for num in range(k):\n",
    "            \n",
    "            while i < n:\n",
    "                c = capital[i]\n",
    "                p = profits[i]\n",
    "                if c <= w:\n",
    "                    heapq.heappush(heap, -p)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "                \n",
    "            if heap:\n",
    "                neg_p = heapq.heappop(heap)\n",
    "                w += - neg_p \n",
    "            else:\n",
    "                break \n",
    "\n",
    "        return w\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        projects = sorted(zip(profits, capital), key=lambda x: x[0])\n",
    "        pc_list = []\n",
    "        for x in projects:\n",
    "            pc_list.append(list(x))\n",
    "        while(k > 0):\n",
    "            index = value = 0\n",
    "            n = len(pc_list)\n",
    "            i = n - 1\n",
    "            while(i >= 0):\n",
    "                if w >= pc_list[i][1]:\n",
    "                    index, value = i,  pc_list[i][0]\n",
    "                    break\n",
    "                i -= 1\n",
    "            if index == value == 0:\n",
    "                return w\n",
    "            del pc_list[index]\n",
    "            w += value\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        projects = sorted(zip(profits, capital), key=lambda x: x[0])\n",
    "        pc_list = []\n",
    "        for x in projects:\n",
    "            pc_list.append(list(x))\n",
    "        while(k > 0):\n",
    "            index = value = 0\n",
    "            n = len(pc_list)\n",
    "            i = n - 1\n",
    "            while(i >= 0):\n",
    "                if w >= pc_list[i][1]:\n",
    "                    index, value = i,  pc_list[i][0]\n",
    "                    break\n",
    "                i -= 1\n",
    "            if index == value == 0:\n",
    "                return w\n",
    "            del pc_list[index]\n",
    "            w += value\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict, SortedList\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        available_profits = SortedList(key=lambda x:-x)\n",
    "        remain_capitals = SortedDict()\n",
    "        for p, c in zip(profits, capital):\n",
    "            if c not in remain_capitals:\n",
    "                remain_capitals[c] = []\n",
    "            remain_capitals[c].append(p)\n",
    "\n",
    "        while k > 0:\n",
    "            # 将所有需要的本金小于等于当前资本的项目加入最大堆\n",
    "            # 不能再遍历时删除元素\n",
    "            del_cs = list()\n",
    "            for c, ps in remain_capitals.items():\n",
    "                if c>w:\n",
    "                    break\n",
    "                available_profits.update(ps)\n",
    "                del_cs.append(c)\n",
    "            for c in del_cs:\n",
    "                remain_capitals.pop(c)\n",
    "\n",
    "            while len(available_profits) > k:\n",
    "                available_profits.pop()\n",
    "\n",
    "            if len(available_profits) == 0:\n",
    "                break\n",
    "\n",
    "            w += available_profits.pop(0)\n",
    "            k -= 1\n",
    "\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "\n",
    "        if w < min(capital):\n",
    "            return w\n",
    "\n",
    "        arr = [(profits[i], capital[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x:[x[1], -x[0]])\n",
    "        # print(arr)\n",
    "\n",
    "        hq = []\n",
    "        cur = 0  \n",
    "        for i in range(k):\n",
    "            while cur < n and w >= arr[cur][1]:\n",
    "                heapq.heappush(hq, -arr[cur][0])\n",
    "                cur += 1\n",
    "            if not hq:\n",
    "                return w\n",
    "            res = heapq.heappop(hq)\n",
    "            w -= res\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital): \n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(len(profits)):\n",
    "            if capital[i] not in dic:\n",
    "                dic[capital[i]] = [profits[i]]\n",
    "            else:\n",
    "                dic[capital[i]].append(profits[i])\n",
    "        # print(dic)\n",
    "        heap = []\n",
    "        start = 0\n",
    "        for _ in range(k):\n",
    "            limit = min(w + 1, max(capital) + 1)\n",
    "            # print(limit)\n",
    "            for j in range(start, limit):\n",
    "                if j in dic:\n",
    "                    for item in dic[j]:\n",
    "                        heapq.heappush(heap, -item)\n",
    "                        # print(heap)\n",
    "            \n",
    "            if not heap:\n",
    "                return w\n",
    "            start = w + 1\n",
    "            w -= heapq.heappop(heap)\n",
    "            # print(w)\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital): \n",
    "            return w + sum(heapq.nlargest(k, profits))\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(len(profits)):\n",
    "            if capital[i] not in dic:\n",
    "                dic[capital[i]] = [profits[i]]\n",
    "            else:\n",
    "                dic[capital[i]].append(profits[i])\n",
    "        # print(dic)\n",
    "        heap = []\n",
    "        start = 0\n",
    "        for _ in range(k):\n",
    "            limit = min(w + 1, max(capital) + 1)\n",
    "            # print(limit)\n",
    "            for j in range(start, limit):\n",
    "                if j in dic:\n",
    "                    for item in dic[j]:\n",
    "                        heapq.heappush(heap, -item)\n",
    "                        # print(heap)\n",
    "            \n",
    "            if not heap:\n",
    "                return w\n",
    "            start = w + 1\n",
    "            w -= heapq.heappop(heap)\n",
    "            # print(w)\n",
    "\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Profit:\n",
    "    def __init__(self, profit, capital):\n",
    "        self.profit = profit\n",
    "        self.capital = capital\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.profit > other.profit\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        heap = []\n",
    "        items = []\n",
    "        for i in range(len(profits)):\n",
    "            item = Profit(profits[i], capital[i])\n",
    "            if item.capital <= w:\n",
    "                heapq.heappush(heap, item)\n",
    "            else:\n",
    "                items.append(item)\n",
    "\n",
    "        index = 0\n",
    "        while index < k and len(heap):\n",
    "            item = heapq.heappop(heap)\n",
    "            for new_item in items:\n",
    "                if new_item.capital > w and new_item.capital <= w + item.profit:\n",
    "                    heapq.heappush(heap, new_item)\n",
    "            w += item.profit\n",
    "            index += 1\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Queue:\n",
    "        def __init__(self):\n",
    "            from heapq import heappush, heappop\n",
    "            self.data = []\n",
    "        \n",
    "        def push(self, priority, item):\n",
    "            heappush(self.data, (priority, item))\n",
    "\n",
    "        def pop(self):\n",
    "            return heappop(self.data)[1]\n",
    "        \n",
    "        def __len__(self):\n",
    "            return len(self.data)\n",
    "\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        projects = [(capital[i], profits[i]) for i in range(n)]\n",
    "        projects.sort(key=lambda x:x[0])\n",
    "\n",
    "        q = self.Queue()\n",
    "        i = 0\n",
    "        while k > 0:\n",
    "            while i < n and projects[i][0] <= w:\n",
    "                q.push(-projects[i][1], projects[i][1])\n",
    "                i += 1\n",
    "            if len(q) > 0:\n",
    "                w += q.pop()\n",
    "                k -= 1\n",
    "            else:\n",
    "                break\n",
    "        return w\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        proj = []\n",
    "        for profit, cap in zip(profits, capital):\n",
    "            heapq.heappush(proj, (-profit, cap))\n",
    "        res = w\n",
    "        while k > 0 and proj:\n",
    "            tmp = list()\n",
    "            profit, cap = heapq.heappop(proj)\n",
    "            while proj and cap > res:\n",
    "                tmp.append((profit, cap))\n",
    "                profit, cap = heapq.heappop(proj)\n",
    "            \n",
    "            if cap <= res:\n",
    "                res += (-profit)\n",
    "                for x, y in tmp:\n",
    "                    heapq.heappush(proj, (x, y))\n",
    "                k -= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class CompareC:\n",
    "    def __init__(self, profits, capital):\n",
    "        self.profits = profits\n",
    "        self.capital = capital\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.capital < other.capital\n",
    "\n",
    "\n",
    "class CompareP:\n",
    "    def __init__(self, profits, capital):\n",
    "        self.profits = profits\n",
    "        self.capital = capital\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.profits > other.profits\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:\n",
    "        unlock = queue.PriorityQueue()\n",
    "        lock = queue.PriorityQueue()\n",
    "        for i in range(len(profits)):\n",
    "            unlock.put(CompareC(profits[i], capital[i]))\n",
    "        while k > 0:\n",
    "            while not unlock.empty():\n",
    "                if unlock.queue[0].capital <= w:\n",
    "                    tmp = unlock.get()\n",
    "                    lock.put(CompareP(tmp.profits, tmp.capital))\n",
    "                else:\n",
    "                    break\n",
    "            if lock.empty():\n",
    "                return w\n",
    "            w += lock.get().profits\n",
    "            k -= 1\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        arr = sorted(zip(capital, profits), key=lambda i: (i[0], -i[1]))\n",
    "        heap = []\n",
    "        j = 0\n",
    "        ans = w\n",
    "        # print(arr)\n",
    "        for i in range(k):\n",
    "            while j < len(arr) and arr[j][0] <= ans:\n",
    "                heapq.heappush(heap, -arr[j][1])\n",
    "                j += 1\n",
    "            if heap:\n",
    "               ans += -heapq.heappop(heap) \n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        pc = list(zip(profits,capital))\n",
    "        pc.sort(key=lambda x:(x[1],-x[0]))\n",
    "        import heapq\n",
    "        heap = []\n",
    "        num = 0\n",
    "        curp = w\n",
    "        idx = 0\n",
    "        while num < k:\n",
    "            while idx < n and pc[idx][1] <= curp:\n",
    "                heapq.heappush(heap, -pc[idx][0])\n",
    "                idx += 1\n",
    "            if len(heap) == 0:\n",
    "                break\n",
    "            curp += -heapq.heappop(heap)\n",
    "            num += 1\n",
    "        \n",
    "        return curp\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # DP is still slow in this problem\n",
    "        dp = [w]*(k+1)\n",
    "        for p,c in pc:\n",
    "            for i in range(k,-1,-1):\n",
    "                if i == 0:\n",
    "                    break\n",
    "                if dp[i-1] < c:\n",
    "                    break\n",
    "                else:\n",
    "                    dp[i] = max(dp[i], dp[i-1]+p)\n",
    "            if i == k:\n",
    "                break\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, nums, tar):\n",
    "        left, right = 0, len(nums)\n",
    "        while (left<right):\n",
    "            mid = left + (right-left)//2\n",
    "            if nums[mid] < tar:\n",
    "                left = mid + 1\n",
    "            else: \n",
    "                right = mid\n",
    "        nums.insert(left, tar)\n",
    "\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        capPro = collections.defaultdict(list)\n",
    "        sortCap = []\n",
    "        for i in range(len(profits)):\n",
    "            if capital[i] in capPro.keys():\n",
    "                capPro[capital[i]].append(profits[i])\n",
    "            else:\n",
    "                capPro[capital[i]] = [profits[i]]\n",
    "                self.insert(sortCap, capital[i])\n",
    "        #print(capPro)\n",
    "        #print(sortCap)\n",
    "\n",
    "        i = 0\n",
    "        heap = []\n",
    "        for n in range(k):\n",
    "            while (i<len(sortCap) and w>=sortCap[i]):\n",
    "                for pro in capPro[sortCap[i]]:\n",
    "                    heappush(heap, -pro)\n",
    "                i += 1\n",
    "            #print(heap)\n",
    "            if len(heap)>0: \n",
    "                w -= heappop(heap)\n",
    "            print(w)\n",
    "        \n",
    "        return w\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "\n",
    "        if w >= max(capital):\n",
    "            w += sum(sorted(profits, reverse=True)[:k])\n",
    "            return w\n",
    "\n",
    "        proj_dict = dict()\n",
    "        for kk, v in enumerate(zip(profits, capital)):\n",
    "            proj_dict.setdefault(kk, v)\n",
    "        print('proj_dict', proj_dict)\n",
    "        tmp_p = 0\n",
    "        while k:\n",
    "            tmp_p = 0\n",
    "            tmp_num = -1\n",
    "            for num, value in proj_dict.items():\n",
    "                if w >= value[1] and tmp_p < value[0]:\n",
    "                    tmp_p = value[0]\n",
    "                    tmp_num = num\n",
    "            print('p:', tmp_p)\n",
    "            print('num:', tmp_num)\n",
    "            print('front_k', k)\n",
    "            if tmp_num > -1:\n",
    "                w += tmp_p\n",
    "                proj_dict.pop(tmp_num)\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "            print('k', k)\n",
    "        \n",
    "        return w\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        if w>=max(capital):\n",
    "            return w+sum(nlargest(k,profits))\n",
    "        \n",
    "        n=len(profits)\n",
    "        curr=0\n",
    "        arr=[(capital[i],profits[i]) for i in range(n)]\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        \n",
    "        pq=[]\n",
    "        for _ in range(k):\n",
    "            while curr<n and arr[curr][0]<=w:\n",
    "                heappush(pq,-arr[curr][1])\n",
    "                curr+=1\n",
    "                print(pq)\n",
    "            \n",
    "            if pq:\n",
    "                w-=heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        return w\n",
    "        \"\"\"\n",
    "        if w>=max(capital):\n",
    "            return w+sum(sorted(profits,reverse=True)[:k])       \n",
    "        n=len(profits)\n",
    "\n",
    "        # 以利润和最小启动资本的形式存到列表中\n",
    "        \n",
    "        \n",
    "        pc=[(profits[i],capital[i]) for i in range(n)]\n",
    "        # 先按照利润降序，再按照最小启动资本升序，优先选择利润高、启动资本小的项目\n",
    "        pc.sort(key=lambda x: (-x[0], x[1]))\n",
    "\n",
    "        \n",
    "        mask=[False]*n\n",
    "        for _ in range(k):\n",
    "            i=0\n",
    "            # 若当前项目已经完成或者启动资本不够，则看下面的项目\n",
    "            while i<n and (mask[i] or pc[i][1]>w):\n",
    "                i+=1\n",
    "            if i==n:\n",
    "                return w\n",
    "            mask[i]=True\n",
    "\n",
    "            w+=pc[i][0]\n",
    "        return w\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self):\n",
    "        self.list = []\n",
    "        self.size = 0\n",
    "    \n",
    "    def push(self,node):\n",
    "        self.list.append(node)\n",
    "        self.size += 1\n",
    "        self.heapInsert(self.size-1)\n",
    "    \n",
    "    def heapInsert(self,cur):\n",
    "        while cur > 0:\n",
    "            parent = (cur-1)//2\n",
    "            if self.list[parent].profit < self.list[cur].profit:\n",
    "                self.list[parent], self.list[cur] = self.list[cur],self.list[parent]\n",
    "                cur = parent #这里最开始忘了\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def heapify(self,cur):\n",
    "        while 2*cur+1 < self.size:\n",
    "            largest = 2*cur+1\n",
    "            if 2*cur+2 <self.size and self.list[2*cur+2].profit > self.list[largest].profit:\n",
    "                largest = 2*cur+2\n",
    "            \n",
    "            if self.list[largest].profit>self.list[cur].profit:\n",
    "                self.list[largest],self.list[cur] = self.list[cur],self.list[largest]\n",
    "                cur = largest #这里最开始忘了\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def pop(self):\n",
    "        self.list[0],self.list[self.size-1] = self.list[self.size-1],self.list[0]\n",
    "        pop = self.list.pop()\n",
    "        self.size -= 1 #这里最开始忘了\n",
    "        self.heapify(0)\n",
    "        return pop\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,p,c):\n",
    "        self.profit = p\n",
    "        self.capital = c\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        n = len(profits)\n",
    "        #想到了用堆，但是没想到先按capital排序，不然只能做k次扫描，还需要visited集合或者new_arr记录还没加入过的project\n",
    "        arr = [Node(profits[i],capital[i]) for i in range(n)]\n",
    "        heap = Heap()\n",
    "        arr.sort(key=lambda x: x.capital)\n",
    "        cur = 0\n",
    "        while k > 0:\n",
    "            while cur < n and arr[cur].capital<=w:\n",
    "                heap.push(arr[cur])\n",
    "                cur += 1\n",
    "            \n",
    "            if heap.size > 0:\n",
    "                w += heap.pop().profit\n",
    "                k -= 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        class profitFirst:\n",
    "            def __init__(self, profit, capital):\n",
    "                self.profit = profit\n",
    "                self.capital = capital\n",
    "            \n",
    "            def __lt__(self, item):\n",
    "                return self.profit < item.profit\n",
    "\n",
    "            def __str__(self):\n",
    "                return f\"({self.profit},{self.capital})\"\n",
    "\n",
    "            def __repr__(self):\n",
    "                return self.__str__()\n",
    "        \n",
    "        class capitalFirst:\n",
    "            def __init__(self, profit, capital):\n",
    "                self.profit = profit\n",
    "                self.capital = capital\n",
    "            \n",
    "            def __lt__(self, item):\n",
    "                    return self.capital < item.capital\n",
    "\n",
    "            def __str__(self):\n",
    "                return f\"({self.profit},{self.capital})\"\n",
    "            \n",
    "            def __repr__(self):\n",
    "                return self.__str__()\n",
    "\n",
    "        projects = [profitFirst(-profits[i],capital[i]) \n",
    "                                for i in range(len(profits)) if capital[i] <= w]\n",
    "        heapq.heapify(projects)\n",
    "\n",
    "        n_projects = [capitalFirst(profits[i],capital[i]) \n",
    "                                for i in range(len(profits)) if capital[i] > w]\n",
    "        # heapq._heapify_max(n_projects)\n",
    "        heapq.heapify(n_projects)\n",
    "\n",
    "        capital = w\n",
    "        while k>0 and len(projects)>0:\n",
    "            # print(projects)\n",
    "            p = heapq.heappop(projects)\n",
    "            # print(p)\n",
    "            capital -= p.profit\n",
    "            while len(n_projects)>0 and n_projects[0].capital <= capital:\n",
    "                n_p = heapq.heappop(n_projects)\n",
    "                # print(n_p)\n",
    "                heapq.heappush(projects, profitFirst(-n_p.profit,n_p.capital))\n",
    "            k -= 1\n",
    "        return capital\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
